class TreeNode:
    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None


def constructBT(nums):
    if not nums:
        return None
    maxVal = float("-inf")

    index = 0

    for i in range(len(nums)):
        if nums[i] > maxVal:
            maxVal = nums[i]
            index = i

    root = TreeNode(maxVal)
    root.left = constructBT(nums[:index])
    root.right = constructBT(nums[index + 1:])
    return root


nums = [3, 2, 1, 6, 0, 5]
root = constructBT(nums)


def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)


preorder(root)


class LNode:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        self.head = LNode(data[0])
        p = self.head
        for i in data[1:]:
            node = LNode(i)
            p.next = node
            p = p.next

    def traveList(self):
        p = self.head
        while p:
            print(p.data)
            p = p.next


def sortedListedToBST(head):
    def getMedian(left, right):
        fast = slow = left
        while fast != right and fast.next != right:
            fast = fast.next.next
            slow = slow.next
        return slow

    def buildTree(left, right):
        if left == right:
            return None

        mid = getMedian(left, right)
        root = TreeNode(mid.data)
        root.left = buildTree(left, mid)
        root.right = buildTree(mid.next, right)
        return root

    return buildTree(head, None)

data = [1, 2, 3, 4, 5, 6, 7, 8]
linked = LinkList()
ldata = linked.initList(data)
linked.traveList()
bst = sortedListedToBST(linked.head)
preorder(bst)


